package com.tgy.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

public class _剑指_Offer_40_最小的k个数_01 {

    public static int[] getLeastNumbers(int[] arr, int k) {

        if (k == 0) {

            return new int[]{};
        }

        int len = arr.length;
        if (k == len) {

            return arr;
        }

        quickSort(arr,0,len - 1,k-1);

        int[] res = new int[k];

        for (int i = 0; i < k; i++) {

            res[i] = arr[i];
        }

        return res;
    }

    private static void quickSort(int[] arr, int start, int end, int k) {

        if (start >= end) {

            return;
        }

        int val = arr[start];

        int left = start,right = end;

        while (left < right) {

            while (left < right && val < arr[right]) {

                right--;
            }

            if (left < right) {

                arr[left++] = arr[right];
            }


            while (left < right && val > arr[left]) {

                left++;
            }

            if (left < right) {

                arr[right--] = arr[left];
            }
        }

        arr[left] = val;

        if (k > left) {

            quickSort(arr,left+1,end,k);
        }else if (k < left) {
            quickSort(arr,start,left - 1,k);
        }
    }

    public static void main(String[] args) {

        int[] nums = {1,4,2,5,6,3,7,1};
        System.out.println(Arrays.toString(getLeastNumbers(nums, 5)));
    }
}
